##15. 三数之和
'''
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
'''

#双指针法 对数组排序后，使用for循环i，同时left=i+1和right=len(n)-1分别向左和向右移动，相遇时结束，即可遍历(i,left,right)
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        if len(nums) < 3: return []
        nums, res, n = sorted(nums), [], len(nums)
        for i in range(n - 2):
            l, r = i+1, n-1
            if nums[i] > 0: break #nums[i]<=nums[l]<=nums[r] --> nums[i]<0
            if res != [] and res[-1][0] == nums[i]: continue
            #if i >= 1 and nums[i] == nums[i - 1]: continue #和上一句等价
            while l < r:
                if nums[i] + nums[l] + nums[r] == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r-1 and nums[l] == nums[l+1]: l += 1
                    while r > l+1 and nums[r] == nums[r-1]: r -= 1
                if nums[i] + nums[l] + nums[r] > 0: r -= 1
                else: l += 1
        return res